Section: New Results

Non-linear computational geometry

Geometry of robotic mechanisms

Parallel manipulators are a family of mechanisms, the geometry of which is difficult to compute in general. The use of algebraic methods allowed us to describe precisely the geometry of the configurations of different specific parallel manipulators, in collaboration with researchers from the IRCCyN laboratory in Nantes.

More precisely, moving a parallel robot toward specific parametric values can break it. A challenge is to describe this set of singularities. This was adressed for a planar mechanism with three degrees of freedom in [16] and a spatial mechanism with six degrees of freedom in [12] .

Then, a more challenging question arises naturally. Given a familly of mechanisms parametrized by some construction variables, is it possible to find a mechanism that has no singularities? A method based on Gröbner bases was proposed in [17] for a specific family of planar parallel robot with two degrees of freedom.

Solving bivariate systems and topology of algebraic curves

In the context of our algorithm Isotop for computing the topology of algebraic curves [28] , we study the bit complexity of solving a system of two bivariate polynomials of total degree $d$ with integer coefficients of bitsize $\tau$. We focus on the problem of computing a Rational Univariate Representation (RUR) of the solutions, that is, roughly speaking, a univariate polynomial and two rational functions which map the roots of the polynomial to the two coordinates of the solutions of the system.

We work on an algorithm for computing RURs with worst-case bit complexity in $O(d^8+d^7\tau +d^5{\tau }^2)$ (where polylogarithmic factors are omitted). In addition, we show that certified approximations of the real solutions can be computed from this representation with $O(d^8+d^7\tau )$ bit operations. It should be stressed that our algorithm is deterministic and that it makes no genericity assumption.

When $\tau \in O\left(d^2\right)$, this complexity decreases by a factor $d^2$ the best known upper bound for computing Rational Univariate Representations of such systems and it matches the recent best known complexity (Emeliyanenko and Sagraloff, 2012) for “only” computing certified approximations of the solutions. This shows, in particular, that computing RURs of bivariate systems is in a similar class of (known) complexity as computing certified approximations of one of the variables of its real solutions.

This work is on-going and is done in collaboration with Fabrice Rouillier (Inria Ouragan).